// Copyright (C) 2012 Yury Bychenkov (http://bychenkov.com).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//  - Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//  - Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//  - Neither the name of Yury Bychenkov nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef dictionary_h
#define	dictionary_h

#include "common.h"

class Dictionary;

template <typename ElementTraits>
class DictionaryBuilder {
public:
	DictionaryBuilder(uint8* mainMemory, size_t mainMemorySize, uint8* externalMemory, size_t externalMemoryCapacity);
	~DictionaryBuilder();

	bool add(const uint8* element);

	bool build(uint8* buffer, uint64 capacity, uint64& size, uint& count);

private:
	static const uint MAX_INNER_CHUNKS = 32;
	static const uint MAX_SKIP_COUNT = 1024 * 1024;

	struct Chunk {
		uint8* first;
		uint8* last;
		uint8* end;		
		uint8* current;
		uint count;
	};

		     
	void fixHeap(Chunk** heap, int heapSize, int nodeIndex);

	static void copyMemory(uint8* dst, const uint8* src, const uint size);

	bool merge();
   	uint64 flush(uint8* buffer, uint64 capacity, bool mainOnly);

private:
	uint8* const dataStart;
	uint8* const dataEnd;
	uint8* const bufferEnd;

	uint8* const externalMemory;
	const uint64 externalMemoryCapacity;
	uint64 externalMemoryPos;

	Chunk* chunks;
	uint chunkCapacity;
	uint externalChunkCount;
	uint lastChunkIndex;
};

class Dictionary {
public:
	Dictionary(const uint8* data, uint dataSize, uint dataCount, const uint32* skipTable, uint skipStep);

	uint getCount() const;

	template <typename ElementTraits> int find(const void* element) const;
	template <typename ElementTraits> const uint8* get(uint elementIndex) const;

private:
	Dictionary(const uint8* data);

private:
	const uint8* data;
	const uint dataSize;
	const uint dataCount;

	const uint32* skipTable;
	const uint skipStep;
	const uint skipCount;
};


#include "dictionary.hpp"

#endif // dictionary_h
